package com.mlh.linkedlist;

import java.util.PriorityQueue;

/**
 * @author 缪林辉
 * @date 2024/8/22 11:20
 * @DESCRIPTION
 */
//给你一个链表数组，每个链表都已经按升序排列。
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。
public class 合并K个升序链表 {
    //方法一：简单合并，两个链表合并成一个ans，ans在与其他链表一一合并即可
    //方法二：分治合并，链表两两合并，不断向上合并
    //方法三：用优先级队列来优化各个链表节点的排序
    public ListNode method1(ListNode[] lists) {
        PriorityQueue<ListNode> queue=new PriorityQueue<>((o1,o2)->{return o1.val-o2.val;});
        //将所有链表的头结点加入到队列中
        for (ListNode node:lists){
            if(node!=null){
                queue.add(node);
            }
        }
        //sentry为新头的哨兵节点
        ListNode sentry=new ListNode(-1),pre=sentry;
        //开始构建新链表
        while (!queue.isEmpty()){
            pre.next=queue.poll();
            pre=pre.next;
            if(pre.next!=null){
                queue.add(pre.next);
            }
        }
        return sentry.next;
    }

    //使用优先级队列实际上就是所有链表的单个节点进行比较
    public ListNode practice(ListNode[] lists) {
        //优先级队列默认是小根堆
        PriorityQueue<ListNode>queue=new PriorityQueue<>((o1,o2)->{return o1.val-o2.val;});
        for (ListNode node :lists) {
            if(node!=null){
                queue.add(node);
            }
        }
        ListNode sentry=new ListNode(),pre=sentry;
        while(!queue.isEmpty()){
            pre.next=queue.poll();
            pre=pre.next;
            if(pre.next!=null){
                queue.add(pre.next);
            }
        }
        return sentry.next;
    }

    // public static void main(String[] args) {
    //     PriorityQueue<Integer>queue=new PriorityQueue<>();
    //     for (int i = 0; i < 9; i++) {
    //         queue.add(8-i);
    //     }
    //     for (int i = 0; i < 9; i++) {
    //         System.out.println(queue.poll());
    //     }
    // }
}
